home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / DJGPP / LGP250S1.ZIP / src / libgplus.5 / libgplus / tests / tpq.cc < prev    next >
C/C++ Source or Header  |  1993-06-06  |  6KB  |  272 lines
  1. /*
  2.  a test file for PQs
  3. */
  4.  
  5. #ifdef PTIMES
  6. const int ptimes = 1;
  7. #else
  8. const int ptimes = 0;
  9. #endif
  10.  
  11. #include <stream.h>
  12. #include <assert.h>
  13. #include <builtin.h>
  14.  
  15. #define tassert(ex) { cerr << #ex; \
  16.                        if ((ex)) cerr << " OK\n"; \
  17.                        else cerr << " Fail\n"; }
  18.  
  19. #include "iPQ.h"
  20.  
  21.  
  22. int SIZE;
  23.  
  24. int *nums;
  25. int *odds;
  26. int *dups;
  27.  
  28. void add(int x[], intPQ& a)
  29. {
  30.   for (int i = 0; i < SIZE; ++i) a.enq(x[i]);
  31. }
  32.  
  33. #include <MLCG.h>
  34.  
  35. MLCG randgen;
  36.  
  37. void permute(int x[])
  38. {
  39.   for (int i = 1; i < SIZE; ++i)
  40.   {
  41.     int j = randgen.asLong() % (i + 1);
  42.     int tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  43.   }
  44. }
  45.  
  46. void makenums()
  47. {
  48.   for (int i = 0; i < SIZE; ++i) nums[i] = i + 1;
  49.   permute(nums);
  50. }
  51.  
  52. void makeodds()
  53. {
  54.   for (int i = 0; i < SIZE; ++i) odds[i] = 2 * i + 1;
  55.   permute(odds);
  56. }
  57.  
  58. void makedups()
  59. {
  60.   for (int i = 0; i < SIZE; i += 2) dups[i] = dups[i+1] = i/2 + 1;
  61.   permute(dups);
  62. }
  63.  
  64. void printPQ(intPQ& a)
  65. {
  66.   int maxprint = 20;
  67.   cout << "[";
  68.   int k = 0;
  69.   for (Pix i = a.first(); i != 0 && k < maxprint; a.next(i),++k) 
  70.     cout << a(i) << " ";
  71.   if (i != 0) cout << "...]\n";
  72.   else cout << "]\n";
  73. }
  74.  
  75. #include "iXPPQ.h"
  76.  
  77. void XPtest()
  78. {
  79.   intXPPQ a(SIZE);
  80.   add(nums, a);
  81.   intXPPQ b(SIZE);
  82.   add(odds, b);
  83.   intXPPQ c(SIZE);
  84.   add(dups, c); 
  85.   intXPPQ d(a);
  86.   add(nums, d);
  87.   cout << "a: "; printPQ(a);
  88.   cout << "b: "; printPQ(b);
  89.   cout << "c: "; printPQ(c);
  90.   cout << "d: "; printPQ(d);
  91.   assert(a.length() == SIZE);
  92.   assert(b.length() == SIZE);
  93.   assert(c.length() == SIZE);
  94.   assert(d.length() == SIZE*2);
  95.   assert(a.front() == 1);
  96.   assert(b.front() == 1);
  97.   assert(c.front() == 1);
  98.   assert(d.front() == 1);
  99.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  100.   d.del_front();
  101.   assert(d.front() == 1);
  102.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  103.   assert(a.empty());
  104.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  105.   assert(b.empty());
  106.   Pix* indices = new Pix [SIZE];
  107.   int m = 0;
  108.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  109.   assert(m == SIZE/2);
  110.   while (--m >= 0) c.del(indices[m]);
  111.   assert(c.length() == SIZE/2);
  112.   int last = -1;
  113.   j = 0;
  114.   while (!c.empty())
  115.   {
  116.     int current = c.deq();
  117.     assert(last <= current);
  118.     last = current;
  119.     ++j;
  120.   }
  121.   assert(j == SIZE/2);
  122.  
  123.   delete [] indices;
  124.   d.clear();
  125.   assert(d.empty());
  126.   assert(a.OK());
  127.   assert(b.OK());
  128.   assert(c.OK());
  129.   assert(d.OK());
  130. }
  131.  
  132. #include "iPHPQ.h"
  133.  
  134. void PHtest()
  135. {
  136.   intPHPQ a(SIZE);
  137.   add(nums, a);
  138.   intPHPQ b(SIZE);
  139.   add(odds, b);
  140.   intPHPQ c(SIZE);
  141.   add(dups, c); 
  142.   intPHPQ d(a);
  143.   add(nums, d);
  144.   cout << "a: "; printPQ(a);
  145.   cout << "b: "; printPQ(b);
  146.   cout << "c: "; printPQ(c);
  147.   cout << "d: "; printPQ(d);
  148.   assert(a.length() == SIZE);
  149.   assert(b.length() == SIZE);
  150.   assert(c.length() == SIZE);
  151.   assert(d.length() == SIZE*2);
  152.   assert(a.front() == 1);
  153.   assert(b.front() == 1);
  154.   assert(c.front() == 1);
  155.   assert(d.front() == 1);
  156.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  157.   d.del_front();
  158.   assert(d.front() == 1);
  159.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  160.   assert(a.empty());
  161.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  162.   assert(b.empty());
  163.   Pix* indices = new Pix [SIZE];
  164.   int m = 0;
  165.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  166.   assert(m == SIZE/2);
  167.   while (--m >= 0) c.del(indices[m]);
  168.   assert(c.length() == SIZE/2);
  169.   int last = -1;
  170.   j = 0;
  171.   while (!c.empty())
  172.   {
  173.     int current = c.deq();
  174.     assert(last <= current);
  175.     last = current;
  176.     ++j;
  177.   }
  178.   assert(j == SIZE/2);
  179.   delete [] indices;
  180.   d.clear();
  181.   assert(d.empty());
  182.   assert(a.OK());
  183.   assert(b.OK());
  184.   assert(c.OK());
  185.   assert(d.OK());
  186. }
  187.  
  188. #include "iSplayPQ.h"
  189.  
  190. void Splaytest()
  191. {
  192.   intSplayPQ a;
  193.   add(nums, a);
  194.   intSplayPQ b;
  195.   add(odds, b);
  196.   intSplayPQ c;
  197.   add(dups, c); 
  198.   intSplayPQ d(a);
  199.   add(nums, d);
  200.   cout << "a: "; printPQ(a);
  201.   cout << "b: "; printPQ(b);
  202.   cout << "c: "; printPQ(c);
  203.   cout << "d: "; printPQ(d);
  204.   assert(a.length() == SIZE);
  205.   assert(b.length() == SIZE);
  206.   assert(c.length() == SIZE);
  207.   assert(d.length() == SIZE*2);
  208.   assert(a.front() == 1);
  209.   assert(b.front() == 1);
  210.   assert(c.front() == 1);
  211.   assert(d.front() == 1);
  212.   for (int j = 1; j <= SIZE; ++j) assert(a.contains(j));
  213.   d.del_front();
  214.   assert(d.front() == 1);
  215.   for (j = 1; j <= SIZE; ++j) assert(a.deq() == j);
  216.   assert(a.empty());
  217.   for (j = 1; j <= SIZE*2; j+=2) assert(b.deq() == j);
  218.   assert(b.empty());
  219.   Pix* indices = new Pix[SIZE];
  220.   int m = 0;
  221.   for (Pix i = c.first(); i != 0; c.next(i), c.next(i)) indices[m++] = i;
  222.   assert(m == SIZE/2);
  223.   while (--m >= 0) c.del(indices[m]);
  224.   assert(c.length() == SIZE/2);
  225.   int last = -1;
  226.   j = 0;
  227.   while (!c.empty())
  228.   {
  229.     int current = c.deq();
  230.     assert(last <= current);
  231.     last = current;
  232.     ++j;
  233.   }
  234.   assert(j == SIZE/2);
  235.   delete [] indices;
  236.   d.clear();
  237.   assert(d.empty());
  238.   assert(a.OK());
  239.   assert(b.OK());
  240.   assert(c.OK());
  241.   assert(d.OK());
  242. }
  243.  
  244.  
  245.  
  246. int main(int argv, char** argc)
  247. {
  248.   if (argv > 1)
  249.   {
  250.     SIZE = abs(atoi(argc[1]));
  251.     SIZE &= ~1;
  252.   }
  253.   else
  254.     SIZE = 100;
  255.   nums = new int[SIZE];
  256.   odds = new int[SIZE];
  257.   dups = new int[SIZE];
  258.   makenums();
  259.   makeodds();
  260.   makedups();
  261.   start_timer();
  262.   cout << "Splaytest\n"; Splaytest();
  263.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  264.   start_timer();
  265.   cout << "PHtest\n"; PHtest();
  266.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  267.   start_timer();
  268.   cout << "XPtest\n"; XPtest();
  269.   if (ptimes) cout << "\ntime = " << return_elapsed_time(0.0) << "\n";
  270.   return 0;
  271. }
  272.